/**
 * Created by ospip on 2017/11/2.
 * Copyright (c) 2017 LLAP. All rights reserved.
 */
public class LinkedTree<T extends Comparable<? super T>> {
    public TreeNode<T> root;

    public LinkedTree(T data) {
        root = new TreeNode<>(data);
    }

    public LinkedTree(LinkedTree<T> src) {
        root = new TreeNode<>(src.root.data);
        root.children = create(src.root.children, root);
    }

    public TreeNode<T> create(TreeNode<T> r, TreeNode<T> parent) {
        if (r == null) return null;
        TreeNode<T> ret = new TreeNode<>(r.data, parent);
        TreeNode<T> t1, t2;
        for (t1 = r.sibling; t1 != null; t1 = t1.sibling) {
            t2 = new TreeNode<>(t1.data, parent);
            t2.sibling = ret.sibling;
            ret.sibling = t2;
            t2.children = create(t1.children, t2);
        }
        ret.children = create(r.children, ret);

        return ret;
    }


    public void leafToRoot() {
        dfs(this.root, "");
        System.out.println();
    }

    public void dfs(TreeNode<T> t, String path) {
        if (t == null) return;
        path = t.data.toString() + path;
        if (t.children == null) {
            System.out.println(path);
            return;
        }
        for (TreeNode<T> p = t.children; p != null; p = p.sibling) {
            dfs(p, " -> " + path);
        }
    }

    public void setParent(TreeNode<T> child, TreeNode<T> p) {
        child.parent = p;
        if (p.children == null) p.children = child;
        else {
            child.sibling = p.children;
            p.children = child;
        }
    }

    public void setParent(Object c, Object p) {
        if (c instanceof TreeNode<?> && p instanceof TreeNode<?>) {
            this.setParent((TreeNode<T>)c, (TreeNode<T>)p);
        }
    }

    public static void main(String[] args) {
        LinkedTree<String> t = new LinkedTree<>("A");
        Object[] sn = new TreeNode<?>[10];
        for (int i = 1; i < 10; i++) {
            sn[i] = new TreeNode<String>(String.format("%c", 'A' + i));
            //System.out.println(sn[i].toString());
        }

        t.setParent(sn[7], sn[6]);
        t.setParent(sn[8], sn[6]);
        t.setParent(sn[4], sn[1]);
        t.setParent(sn[5], sn[1]);
        t.setParent(sn[6], sn[3]);
        t.setParent(sn[9], sn[3]);
        t.setParent(sn[1], t.root);
        t.setParent(sn[2], t.root);
        t.setParent(sn[3], t.root);

        t.leafToRoot();

        LinkedTree<String> t2 = new LinkedTree<>(t);
        t2.leafToRoot();
    }
}
